using System;
using Fibers;
using System.Collections;

interface TreeVisitor {
	void Visit(Branch branch);
	void Visit(Leaf leaf);
}

interface Tree {
	void Accept(TreeVisitor visitor);
}

class Branch : Tree {
	public Branch(Tree l, Tree r) { left = l; right = r; }
	public void Accept(TreeVisitor visitor) {
		visitor.Visit(this);
	}
	public Tree left, right;
}

class Leaf : Tree {
	public Leaf(Object val) { value = val; }
	public void Accept(TreeVisitor visitor) {
		visitor.Visit(this);
	}
	public Object value;
}

class LeafGenerator : Fiber, TreeVisitor, IEnumerator {

	public enum Order { Left, Right };

	public LeafGenerator(Tree _tree, Order _order) {
		tree = _tree;
		order = _order;
	}

	// TreeVisitor
	public void Visit(Branch branch) {
		if(order == Order.Left) {
			branch.left.Accept(this);
			branch.right.Accept(this);
		} else {
			branch.right.Accept(this);
			branch.left.Accept(this);
		}
	}

	public void Visit(Leaf leaf) {
		Yield(leaf.value);
	}

	protected override void Run() {
		tree.Accept(this);
	}

	// IEnumerator
	public void Reset() {}

	public Object Current { get { return curobj; } }

	public bool MoveNext() {
		curobj = Resume();
		return curobj != null;
	}

	private Tree tree;
	private Object curobj;
	private Order order;
}

class EnumerableTree : IEnumerable {
	public EnumerableTree(Tree _tree, LeafGenerator.Order _order) {
		tree = _tree;
		order = _order;
	}
	public IEnumerator GetEnumerator() {
		return new LeafGenerator(tree, order);
	}
	private Tree tree;
	private LeafGenerator.Order order;
}

class Test {
	static bool MatchFringe(Coroutine nexta, Coroutine nextb) {
		Object a = nexta();
		Object b = nextb();
		Console.WriteLine("a is {0} b is {1}", a, b);
		if(a == null && b == null)
			return true;
		if(a == null || b == null)
			return false;
		if(a.Equals(b))
			return MatchFringe(nexta, nextb);
		else
			return false;
	}


	public static void Main(String[] args)  {
		Tree atree, btree;

		if(args.Length != 1) {
			Console.WriteLine("usage: tree match|unmatch");
			return;
		}

		if(args[0].Equals("match"))
			CreateMatchingTrees(out atree, out btree);
		else
			CreateUnmatchedTrees(out atree, out btree);

		Console.WriteLine("Enumeration example");
		foreach(Object obj in new EnumerableTree(atree,
				LeafGenerator.Order.Right)) {
			Console.WriteLine("object is {0}", obj);
		}

		Console.WriteLine("\nEnumeration example with break");
		foreach(Object obj in new EnumerableTree(atree,
				LeafGenerator.Order.Left)) {
			Console.WriteLine("object is {0}", obj);
			break;
		}

		Console.WriteLine("\nTree matching example");
		LeafGenerator lga = new LeafGenerator(atree,
			LeafGenerator.Order.Left);
		LeafGenerator lgb = new LeafGenerator(btree,
			LeafGenerator.Order.Left);
		
		bool same = MatchFringe(lga, lgb);
		
		if(same)
			Console.WriteLine("LEAFS MATCH");
		else
			Console.WriteLine("LEAFS DO NOT MATCH"); 

		lga.Dispose();
		lgb.Dispose();
	}

	private static void CreateMatchingTrees(out Tree atree, out Tree btree) {
		atree = btree = new Branch(
			new Leaf("1"),
			new Branch(
				new Leaf("2"),
				new Leaf("3")
			)
		);
	}

	private static void CreateUnmatchedTrees(out Tree atree, out Tree btree) {
		atree = new Branch(
			new Leaf("1"),
			new Branch(
				new Leaf("2"),
				new Leaf("3")
			)
		);
		btree = new Branch(
			new Branch(
				new Leaf("1"),
				new Leaf("4")
			),
			new Leaf("3")
		);
	}
}
